/**
 * @author David Young
 */
package csab.core.structs;

import java.awt.Rectangle;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;

import csab.core.Collidable;
/**
 * This class is used to create QuadTrees for collision and rendering purposes.
 * The trees created with these nodes are auto-balanced and can add/remove items
 * at whim.
 * @author David Young
 *
 */
//FIXME FIX PERFORMANCE ISSUES WITH QUADTREENODE
public final class QuadTreeNode {
	/**
	 * Defines the maximum number of items that can be held by a QuadTreeNode
	 * before the elements are propagated to child QuadTreeNodes.
	 */
	public final static int MAX_ITEMS = 5;
	/**
	 * Maximum number of levels within a QuadTree. The depth cannot be
	 * greater than this number.
	 */
	public final static int MAX_LEVELS = 4;
	
	/**
	 * Minimum number of items that the children and grandchildren of this
	 * QuadTreeNode must hold before they are absorbed into the parent.
	 */
	public final static int MIN_SUBITEMS = 1;	
	
	//Children of this QuadTreeNode
	private QuadTreeNode[] children;
	private int current_level;
	
	//Number of items in this subtree
	private int itemcount;
	//List of items in this QuadTreeNode
	private List<Collidable> items;
	//Parent of this QuadTreeNode
	private QuadTreeNode parent;
	//Root of this QuadTreeNode
	private QuadTreeNode root;
	//Area encompassed by QuadTreeNode
	private Rectangle section;
	/**
	 * Constructor which takes one parameter. Used to denote a QuadTreeNode with no
	 * parent node.
	 * @param section Defines the area this QuadTreeNode holds jurisdiction of.
	 * @see Rectangle
	 */
	public QuadTreeNode(Rectangle section)
	{
		this(section, null);
	}
	
	private QuadTreeNode(Rectangle section, QuadTreeNode parent)
	{
		this(section, parent, 0);
	}
	
	private QuadTreeNode(Rectangle section, QuadTreeNode parent, int cl)
	{
		if(parent == null)
			root = this;
		else
			root = parent.root;
		this.section = section;
		current_level = cl;
		itemcount = 0;
		items = new LinkedList<Collidable>();//new ArrayList<Collidable>(MAX_ITEMS + MAX_ITEMS / 2);
		children = null;
		this.parent = parent;
	}
	
	/**
	 * Adds an item to this QuadTreeNode's entire tree structure (i.e. the object
	 * may be contained by this QuadTreeNode, or one of it's children/grandchildren).
	 * @param item The item to be added into the tree structure.
	 * @see Collidable
	 */
	public final void addItem(Collidable item)
	{
		Rectangle cbox = item.getCollisionBox();
		if(!section.contains(cbox))
			throw new NotContainedException("Tried to add item not contained within QuadTreeNode\n" +
											"Item :: " + item + "\n" +
											"QuadTreeNode Section :: x - " + section.x + " y - " + section.y + 
											" width - " + section.width + " height - " + section.height);
		
		itemcount++;
		if(!hasChildren() && itemcount > MAX_ITEMS && current_level + 1 < MAX_LEVELS)
		{
			createChildren();
		}
		
		//We have children and must therefore must check to see if our item
		//can be added to them.
		if(hasChildren())
		{
			boolean isSubbed = false;
			for(QuadTreeNode node : children)
			{
				if(node.section.contains(cbox))
				{
					node.addItem(item);
					isSubbed = true;
					break;
				}
			}
			
			if(!isSubbed)
				if(!items.contains(item))
					items.add(item);
		}
		else
		{
			if(!items.contains(item))
				items.add(item);
		}
	}
	
	/**
	 * Performs collision operations against all Collidable objects that intersect, contain, or
	 * are contained by "item". Operations are called on both entities when a collision occurs.
	 * If the operations modify the positions of the entities and are moved out of the scope of
	 * their respective QuadTreeNodes, they are removed from the subtree and then added again and 
	 * the "doCollisions" operation is ceased. Do not depend on this method for correcting moving objects. 
	 * It is imperative that you test for collisions on movement.
	 * @param item Collidable to check collisions against.
	 * @return true if the method successfully executes, false if a collision causes the method to
	 * fall-through. false may indicate that the method may need to be re-simulated with the object
	 * in order to accurately simulate the object's collision state.
	 * @see Collidable
	 */
	public final boolean doCollisions(Collidable item)
	{
		Rectangle cbox = item.getCollisionBox();
		
		//Perform collisions against children
		if(hasChildren())
		{
			for(QuadTreeNode node : children)
			{
				//If we collide with the node, then check for subcollisions.
				if(node.section.intersects(cbox) ||
				   node.section.contains(cbox))
					node.doCollisions(item);
			}
		}
		
		//Does the collision box collide with our section?
		if(section.intersects(cbox) ||
		   section.contains(cbox))
		{
			for(Collidable it : items)
			{
				//Do a collision check and make sure we don't collide with ourselves
				if(!it.equals(item) && item.collides(it))
				{
					Rectangle ibox = it.getCollisionBox();
					
					//Save positions
					int x1 = cbox.x, y1 = cbox.y,
						x2 = ibox.x, y2 = ibox.y;
					//Perform collisions
					item.doCollide(it);
					it.doCollide(item);
					
					//Did we move at all?
					boolean fellthrough = false;
					
					
					//Delete it if it moved out of section
					if(ibox.x != x2 || ibox.y != y2)
					{
						if(!section.contains(it.getCollisionBox()))
						{
							items.remove(it);
							decAncestors();
							getRoot().addItem(it);
						}
						
						fellthrough = true;
						
					}
					
					//Delete item if it moved out of section
					if(cbox.x != x1 || cbox.y != y1)
					{
						if(!section.contains(cbox))
						{
							items.remove(item);
							decAncestors();
							getRoot().addItem(item);
						}
				
						fellthrough = true;
					}
					
					//Return false and eatChildren if necessary
					if(fellthrough)	
						return false;	
				}
			}
			
			return true;
		} 
		else
			throw new NotContainedException("Tried to perform collisions with an item not intersected or contained by QuadTreeNode\n" +
											"item name/id is :: " + item);
	}
	
	/**
	 * Retrieves the current tree depth.
	 * @return An integer representing the depth of the tree starting from 1.
	 */
	public int getCurrentLevel()
	{
		return current_level + 1;
	}
	
	/**
	 * Returns the number of items (Collidable) contained within this QuadTreeNode as well as child
	 * QuadTreeNodes.
	 * @return The number of Collidable objects within this entire subtree.
	 * @see Collidable
	 */
	public final int getItemCount() { return this.itemcount; }
	
	/**
	 * Returns the number of items (Collidable) actually contained within this node.
	 * @return The number of Collidable objects in this QuadTreeNode.
	 * @see Collidable
	 */
	public final int getOwnedItemCount() { return items.size(); }
	
	/**
	 * Returns the area that this QuadTreeNode entails.
	 * @return The "section", or area, encompassed by this QuadTreeNode.
	 * @see Collidable
	 */
	public final Rectangle getSection() { return this.section; }
	
	/**
	 * Checks to see if this QuadTreeNode has child QuadTreeNodes.
	 * @return true if this QuadTreeNode has child QuadTreeNodes.
	 * @see Rectangle
	 * @see Collidable
	 */
	public final boolean hasChildren() { return this.children != null; }
	
	/**
	 * Checks to see if the item parameter collides with any items within
	 * the tree.
	 * @param item Collidable to check collisions against.
	 * @return true if item collides with another item within the tree, false
	 * if it does not.
	 * @see Collidable
	 */
	public final boolean isColliding(Collidable item)
	{
		Rectangle cbox = item.getCollisionBox();
		
		if(hasChildren())
		{
			for(QuadTreeNode node : children)
			{
				boolean collides = false;
				
				if(node.section.intersects(cbox) ||
				   node.section.contains(cbox))
					collides = node.isColliding(item);
				
				if(collides)
					return true;
			}
		}
		
		if(section.intersects(cbox) ||
				   section.contains(cbox))
		{
			for(Collidable it : items)
			{
				if(!it.equals(item) && item.collides(it))
				{
					return true;
				}
			}
		}

		return false;
	}
	
	/**
	 * 
	 * @param item Collidable to check collisions against.
	 * @return A list of Collidable objects that collided with item.
	 * @see Collidable
	 * @see List
	 */
	public final List<Collidable> queryCollisions(Collidable item)
	{
		Rectangle cbox = item.getCollisionBox();
		List<Collidable> collided = new LinkedList<Collidable>();
		
		if(hasChildren())
		{
			for(QuadTreeNode node : children)
			{
				
				if(node.section.intersects(cbox) ||
				   node.section.contains(cbox))
					collided.addAll(node.queryCollisions(item));
			}
		}
		
		if(section.intersects(cbox) ||
				   section.contains(cbox))
		{
			for(Collidable it : items)
			{
				if(!it.equals(item) && it.collides(item))
				{
					collided.add(it);
				}
			}
		}
		
		return collided;
	}
	
	/**
	 * Remove an item from the tree.
	 * @param item The item to be removed.
	 * @return The true if the item was removed, false if not.
	 * @see Collidable
	 */
	public final boolean removeItem(Collidable item)
	{
		Rectangle cbox = item.getCollisionBox();
		if(items.contains(item))
		{
			items.remove(item);
			decAncestors();
			if(parent != null && parent.itemcount < MIN_SUBITEMS)
				parent.eatChildren();
			if(this.children != null && this.itemcount < MIN_SUBITEMS)
				this.eatChildren();
			return true;
		}
		else if(hasChildren())
		{
			for(QuadTreeNode node : children)
			{
				if(node.section.contains(cbox))
				{
					boolean temp = node.removeItem(item);
					//Check if an item was removed and then do a child check
					if(temp && this.children != null && this.itemcount < MIN_SUBITEMS)
						this.eatChildren();
					return temp;
				}
			}	
		}
		
		return false;
	}
	
	//Create child QuadTreeNodes
	private final void createChildren()
	{
		children = new QuadTreeNode[4];
		int startx = section.x;
		int starty = section.y;
		int subwidth = section.width / 2;
		int subheight = section.height / 2;
		int modw = section.width % 2;
		int modh = section.height % 2;
		//Partition space into four quadrants
		children[0] = new QuadTreeNode(new Rectangle(startx, starty, subwidth, subheight), this, current_level+1);
		children[1] = new QuadTreeNode(new Rectangle(startx + subwidth, starty, subwidth + modw, subheight), this, current_level+1);
		children[2] = new QuadTreeNode(new Rectangle(startx, starty + subheight, subwidth, subheight + modh), this, current_level+1);
		children[3] = new QuadTreeNode(new Rectangle(startx + subwidth, starty + subheight, subwidth + modw, subheight + modh), this, current_level+1);
		
		//Incorporate existing items into child nodes
		Iterator<Collidable> itr = items.iterator();
		while(itr.hasNext())
		{
			Collidable item = itr.next();
			for(QuadTreeNode node : children)
			{
				if(node.section.contains(item.getCollisionBox()))
				{
					node.addItem(item);
					itr.remove();
					break;
				}
			}
		}

		incCurrentLevelAncestors(true);
	}
	
	//Decrement the item count of all ancestor/parent node(s).
	private final void decAncestors()
	{
		QuadTreeNode temp = this;
		while(temp != null)
		{
			temp.itemcount--;
			temp = temp.parent;
		}
	}
	
	//Decrement ancestor nodes
	private final void decCurrentLevelAncestors(boolean isBase)
	{
		if(children != null && getHighestChildLevel() < current_level)
		{
			current_level = getHighestChildLevel();
		}	
		
		if(parent != null)
			parent.decCurrentLevelAncestors(false);
	}
	
	//Take items of child QuadTreeNodes and put them in this nodes item lists
	//then destroy the children.
	private final void eatChildren()
	{
		decCurrentLevelAncestors(true);
		
		for(QuadTreeNode node : children)
		{
			items.addAll(node.items);
		}
		
		children = null;
	}
	
	//Make sure you check to see if children exist
	//or that you check the return value.
	private final int getHighestChildLevel()
	{
		if(children != null)
		{
			int min = 0;
			for(QuadTreeNode node : children)
			{
				if(node.current_level > min && node.getItemCount() > 0)
					min = node.current_level;
			}
			return min;
		}
		else
			return -1;
	}
	
	//Find the root node and return it.
	private final QuadTreeNode getRoot()
	{
		return root;
	}
	
	//Increment ancestor nodes
	private final void incCurrentLevelAncestors(boolean isBase)
	{
		if(isBase)
		{
			current_level++;
		}
		if(children != null && getHighestChildLevel() > current_level)
		{
			current_level = getHighestChildLevel();
		}

		if(parent != null)
			parent.incCurrentLevelAncestors(false);
	}
}